package ljl.alg.wangzheng_camp.round1.stack_and_queue;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class _772_calculate {
    
    public int calculate2(String s) {
        Map<Character, Integer> priority = new HashMap<>();
        priority.put('(', 0);
        priority.put(')', 0);
        priority.put('+', 1);
        priority.put('-', 1);
        priority.put('*', 2);
        priority.put('/', 2);
        
        Deque<Integer> numStack = new LinkedList<>();
        Deque<Character> opStack = new LinkedList<>();
        
        int i = 0;
        int len = s.length();
        while (i < len) {
            if (s.charAt(i) == ' ') {
                i++;
                continue;
            }
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = c - '0';
                i++;
                while (i < len && Character.isDigit(c = s.charAt(i))) {
                    num = num * 10 + c - '0';
                    i++;
                }
                numStack.push(num);
                continue;
            } else if (c == ')') {
                while (opStack.peek() != '(') {
                    calc(numStack, opStack);
                }
                opStack.pop();
            } else {
                while (numStack.size() > 1 && priority.get(c) <= priority.get(opStack.peek())) {
                    calc(numStack, opStack);
                }
                opStack.push(c);
            }
            i++;
        }
        while (!opStack.isEmpty())
            calc(numStack, opStack);
        return numStack.peek();
    }
    void calc(Deque<Integer> numStack, Deque<Character> opStack) {
        numStack.push(calc(opStack.pop(), numStack.pop(), numStack.pop()));
    }
    int calc(char op, int opd2, int opd1) {
        System.out.println(op+", " + opd1+", "+opd2);
        return switch (op) {
            case '+' -> opd1 + opd2;
            case '-' -> opd1 - opd2;
            case '*' -> opd1 * opd2;
            case '/' -> opd1 / opd2;
            default -> 0;
        };
    }
    
    /**
     * tricky 的解法
     * 不推荐
     * 也不好想
     *
     * 操居然还很快
     *
     * */
    public int calculate(String s) {
        return doCalc(s, 0)[0];
    }
    int[] doCalc(String s, int from) {
        int[] pair = new int[2];
        Deque<Integer> nums = new LinkedList<>();
        int len = s.length();
        int num = 0;
        char preOp = '+';
        for (int i = from; i < len; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                int[] group = doCalc(s, i + 1);
                num = group[0];
                i = group[1];
            }
            if (i == len - 1 || !Character.isDigit(c) && c != '(') {
                switch (preOp) {
                    case '+' -> nums.push(num);
                    case '-' -> nums.push(-num);
                    case '*' -> nums.push(nums.pop() * num);
                    case '/' -> nums.push(nums.pop() / num);
                }
                if (c == ')') {
                    pair[1] = i;
                    break;
                }
                num = 0;
                preOp = c;
            }
        }
        int res = 0;
        while (!nums.isEmpty())
            res += nums.pop();
        pair[0] = res;
        
        return pair;
    }
}
